package 中等.树;

import java.util.HashSet;
import java.util.Set;

/**
 * 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词
 * ，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
 * 实现 MagicDictionary 类：
 * MagicDictionary() 初始化对象
 * void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构
 * ，dictionary 中的字符串互不相同
 * bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中
 * 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，
 * 返回 true ；否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/implement-magic-dictionary
 */
public class 实现一个魔法字典_676 {

    public static void main(String[] args) {

    }

}

/**
 * 字典树+深度搜索
 */
class MagicDictionary {

    private Trie trie = new Trie();

    public MagicDictionary() {

    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            trie.insert(s);
        }
    }

    public boolean search(String searchWord) {
        return bfs(trie, searchWord, 0, false);
    }

    public boolean bfs(Trie trie, String word, int index, boolean modify) {
        if (index == word.length()) {
            return trie.end && modify;
        }

        char c = word.charAt(index);
        if (trie.children[c - 'a'] != null) {
            if (bfs(trie.children[c - 'a'], word, index + 1, modify)) {
                return true;
            }
        }
        if (!modify) {
            for (int i = 0; i < 26; i++) {
                if (i != c - 'a' && trie.children[i] != null) {
                    if (bfs(trie.children[i], word, index + 1, true)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }


    private static class Trie {

        public boolean end;

        public Trie[] children;

        public Trie() {
            children = new Trie[26];
        }

        public void insert(String word) {
            char[] letters = word.toCharArray();
            Trie curTree = this;

            for (int i = 0; i < letters.length; i++) {
                int index = letters[i] - 'a';
                // 当前树层的字母没有对应的字符
                if (curTree.children[index] == null) {
                    curTree.children[index] = new Trie();
                    System.out.println();
                }
                curTree = curTree.children[index];
            }
            // 最后一个字母需要做标记
            curTree.end = true;
        }
    }
}

class MagicDictionary2 {

    private Set<String> set = new HashSet<>();

    public MagicDictionary2() {

    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            set.add(s);
        }
    }

    public boolean search(String searchWord) {
        boolean flag = false;
        if (set.contains(searchWord)) {
            set.remove(searchWord);
            flag = true;
        }
        char[] chars = searchWord.toCharArray();
        for (int i = 0; i < searchWord.length(); i++) {
            char curChar = searchWord.charAt(i);
            for (int j = 0; j < 26; j++) {
                chars[i] = (char) (j + 'a');
                if (set.contains(new String(chars))) {
                    if (flag) set.add(searchWord);
                    return true;
                }
            }
            chars[i] = curChar;
        }
        if (flag) set.add(searchWord);
        return false;
    }

}